package com.ken.algorithms.tree;


import java.util.Scanner;
import java.util.Stack;

/**
 * <ul>
 * <li>Title: CD169Main</li>
 * <li>Description:
 * 【题目描述】：
 *
 * 一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。
 * (每个节点的值各不相同)
 * </li>
 * </ul>
 *
 * @author swc
 * @date 2021-09-15 17:18
 */
public class CD169Main {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入节点总数和根节点总数:");
        sc.nextLine(); // 第一行没啥用
        TreeNode root = TreeUtil.createTreeNode(sc);

        TreeNode[] res = getTwoErrorNodes(root);
        System.out.print(res[1].getVal() + " " + res[0].getVal());
    }


    private static TreeNode[] getTwoErrorNodes(TreeNode root) {

        if(root==null){
            return null;
        }

        TreeNode[] res = new TreeNode[2];
        Stack<TreeNode> stack =new Stack<>();

        TreeNode cur =root;
        TreeNode pref =root;

        while (cur!=null || !stack.isEmpty()){
            if(cur!=null){
                stack.push(cur);
                cur = cur.getLeft();
            }else{//处理的是右节点
                cur = stack.pop();
                if(pref!=null && pref.getVal()>cur.getVal()){
                    res[0] = (res[0] == null ? pref : res[0]);//前置节点放在前面
                    res[1] = cur;
                }
                pref = cur;//前置节点
                cur = cur.getRight();//右节点变为当前节点
            }
        }
        return res;
    }

}
